/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class MostStonesRemovedwithSameRoworColumn {
	class Cord {
		int x, y;

	}

	public int removeStones(int[][] stones) {
		System.out.println(stones.length);
		Map<Integer, Set<String>> cordX = new HashMap<>();
		Map<Integer, Set<String>> cordY = new HashMap<>();
		Set<int[]> cords = new HashSet<>();
		for (int[] cord : stones) {
			putMap(cord, cord[0], cordX);
			putMap(cord, cord[1], cordY);
			cords.add((cord));
		}
		int moveCnt = 0;
		while (true) {
			int jiao = findMinJiao(cords, cordX, cordY);
			if (jiao == MAX) {
				break;
			}
			// 移除该点，并更新
			cords.remove(target);
			CordRmv(target, target[0], cordX);
			CordRmv(target, target[1], cordY);
			moveCnt++;
		}
		return moveCnt;
	}

	private void CordRmv(int[] target, int i, Map<Integer, Set<String>> cordX) {
		cordX.get(i).remove(toStr(target));
	}

	int MAX = 2000;

	int[] target = null;

	private int findMinJiao(Set<int[]> cords, Map<Integer, Set<String>> cordX, Map<Integer, Set<String>> cordY) {
		int min = MAX;
		for (int[] cord : cords) {
			int jiao = cordX.get(cord[0]).size() + cordY.get(cord[1]).size();
			if (jiao != 2 && jiao < min) {
				min = jiao;
				target = cord;
			}
		}
		return min;
	}

	private void putMap(int[] cord, int i, Map<Integer, Set<String>> cordX) {
		if (cordX.containsKey(i)) {
			cordX.get(i).add(toStr(cord));
		} else {
			Set<String> set = new HashSet<>();
			set.add(toStr(cord));
			cordX.put(i, set);
		}
	}

	private String toStr(int[] cord) {
		return cord[0] + "_" + cord[1];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] stones = { { 5, 9 }, { 9, 0 }, { 0, 0 }, { 7, 0 }, { 4, 3 }, { 8, 5 }, { 5, 8 }, { 1, 1 }, { 0, 6 },
				{ 7, 5 }, { 1, 6 }, { 1, 9 }, { 9, 4 }, { 2, 8 }, { 1, 3 }, { 4, 2 }, { 2, 5 }, { 4, 1 }, { 0, 2 },
				{ 6, 5 } };
		System.out.println(new MostStonesRemovedwithSameRoworColumn().removeStones(stones));
	}

}
